題目

題目翻譯

有一個 Linked List ，將 k 個節點為一組，並且將這一組內部的元素進行反轉，如果節點總數不足 k 個就不用反轉，最後回傳反轉後的結果

解題思路

1. 初始化：

   • 創建一個 dummy 節點，將其 next 指向 head，用以簡化頭節點的操作。
   • 設置指針 pre 指向每組節點的前一個節點，cur 用來遍歷鏈表。

2. 遍歷與反轉：

   • 遍歷鏈表，每經過 k 個節點，就調用 reverseOneGroup 來反轉這一組節點。
   • 當剩餘節點不足 k 個時，保持原順序不變。

3. 反轉單組節點：

   • 在 reverseOneGroup 中，使用指針操作將每個節點插入到 pre 之後，直到這組節點被完全反轉。

4. 返回結果：

   • 最後返回 dummy->next，即反轉後的鏈表頭節點。

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;

        // 初始化 dummy 節點，指向 head
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;

        int i = 0;
        while (cur) {
            ++i;
            // 當走過 k 個節點時反轉這一組節點
            if (i % k == 0) {
                pre = reverseOneGroup(pre, cur->next);
                cur = pre->next;  // 更新 cur 到下一組的開始節點
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }

    // 反轉一組節點，返回反轉後這一組的尾節點
    ListNode* reverseOneGroup(ListNode* pre, ListNode* next) {
        ListNode *last = pre->next;  // 這組的第一個節點
        ListNode *cur = last->next;  // 這組的第二個節點
        while (cur != next) {
            last->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = last->next;  // 更新 cur 到下一個節點
        }
        return last;  // 返回這一組反轉後的最後一個節點
    }
};